/**
 * 计数排序
 *
 * @param {number[]} nums
 * @return {number[]}
 */
function countingSort(nums) {
  const length = nums.length;
  if (length < 2) {
    return nums;
  }
  let min = nums[0];
  let max = nums[0];
  for (let i = 1; i < length; i++) {
    min = Math.min(min, nums[i]);
    max = Math.max(max, nums[i]);
  }
  const size = max - min + 1;
  const list = Array(size).fill(0);
  for (let i = 0; i < length; i++) {
    list[nums[i] - min]++;
  }
  // 无序
  // const result = [];
  // for (let i = 0; i < size; i++) {
  //   while (list[i] > 0) {
  //     list[i]--;
  //     result.push(i + min);
  //   }
  // }
  // 有序，能够知道排名
  let sum = 0;
  for (let i = 0; i < size; i++) {
    sum += list[i];
    list[i] = sum;
  }
  const result = Array(length);
  for (let i = length - 1; i >= 0; i--) {
    result[list[nums[i] - min] - 1] = nums[i];
    list[nums[i] - min]--;
  }
  return result;
}

const nums = [3, 44, 38, 5, 47, 15, 36, 26, 27, 2, 46, 4, 19, 50, 48];
const nums2 = [9, 3, 5, 4, 9, 1, 2, 7, 8, 1, 3, 6, 5, 3, 4, 0, 10, 9, 7, 9];
console.log(countingSort(nums));
console.log(countingSort(nums2));

module.exports.countingSort = countingSort;
